字符串问题——括号字符串的有效性和最长有效长度

Posted on | In ,

题目：给定一个字符串，判读是不是整体有效的括号字符串。
例：
str=”()”，返回true
str=”(())”，返回true
str=”())”，返回false
str=”()a()”，返回false
实现

  1. 遍历str，若不是括号，则直接返回false。
  2. 遍历到每个字符，检查括号的数量，如果’)’更多，则返回false。
  3. 遍历完，若’(‘的数量和’)’相等，则返回true，否则返回false。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static boolean isValidKuohao (String str) {
		if (str == null || str.equals("")) {
			return false;
		}
		char[] chas = str.toCharArray();
		int num = 0; //遇到左括号则加1，遇到有括号则减1
		for (int i = 0; i < chas.length; i++) {
			if (chas[i] != '(' && chas[i] != ')') { 
				return false;
			}
			if (chas[i] == ')' && --num < 0) { //若右括号数大于左括号数
				return false;
			}
			if (chas[i] == '(') {
				num++;
			}
		}
		return num == 0; //如果最终右括号数-左括号数=0，则返回true，否则返回false
	}

补充题目：给定一个括号字符串str，返回最长的有效括号子串。
例：
str=”(()())”，返回6
str=”())”，返回2
str=”()(()()(“，返回4
实现：动态规划

  1. 生成dp[N]数组，dp[i]表示在str[0,…i]中以str[i]结尾的字符的最长有效括号子串的长度。
  2. dp[0]=0
  3. 从左到右依次遍历str[1,…N-1]，假设遍历到str[i]
    1）若str[i]==’(‘，由于括号一定是以’)’结尾，所以以’(‘结尾是不可能的，dp[i]=0
    2）若str[i]==’)’，